局部性|解法_图计算的学习与思考

篇首语：本文由编程笔记#小编为大家整理，主要介绍了图计算的学习与思考相关的知识，希望对你有一定的参考价值。

好的软件不是靠程序分析、查错查出来的&＃xff0c;而是由正确的人构建出来的。

图成为日益重要的运算对象&＃xff0c;图结构是对群体关系的一种抽象&＃xff0c;可以描述丰富的对象和关系。图计算的核心是如何将数据建模为图结构以及如何将问题的解法转化为图结构上的计算问题&＃xff0c;当问题涉及到关联分析时&＃xff0c;图计算往往能够使得问题的解法很自然地表示为一系列对图结构操作和计算的过程。例如&＃xff0c;使用基于网页链接的图结构的PageRank算法得到网页权重&＃xff0c;作为搜索引擎排序的参考&＃xff0c;利用图结构的用户行为数据来得到精确的群体偏好分析和个性化产品推荐结果。

1.什么是图计算&＃xff1f;

图计算是研究人类世界的事物和事物之间的关系&＃xff0c;对其进行描述、刻画、分析和计算的一门技术。这里的图是“graph”&＃xff0c;而不是图“image”&＃xff0c;源自于数学中的图论&＃xff08;graph theory&＃xff09;。

图是一种最为灵活的连接方式&＃xff0c;让实体之间可以不受限制地连接。图计算不仅仅只是一个技术&＃xff0c;更是一种理解世界的方式。图数据可以很好地描述事物之间的联系&＃xff0c;包括描述联系的方向和属性。从数据结构上看&＃xff0c;图是对事物之间关系的一种原生表达。在某种程度上&＃xff0c;关系数据库应该叫表数据库&＃xff0c;而图数据库反而应该叫关系数据库。广义的图计算是指基于图数据来做各种各样的处理&＃xff0c;包括了图数据库。

图计算技术解决了传统的计算模式下关联查询的效率低、成本高的问题&＃xff0c;在问题域中对关系进行了完整的刻画&＃xff0c;并且具有丰富、高效和敏捷的数据分析能力&＃xff0c;其特征有如下&＃xff1a;

• 基于图抽象的数据模型

• 图数据模型并行抽象

• 图模型系统优化

对于图计算而言&＃xff0c;性能成本、容错机制以及可拓展性都是非常重要的。

2. 从历史发展看图计算

图计算最早可追溯到 20 世纪 60 年代面向树状结构的数据库&＃xff0c;70-80 年代出现面向属性图的模型和技术&＃xff0c;如 LDM&＃xff08;逻辑数据模型&＃xff09;等。直到2007 年&＃xff0c;第一款商用图数据库 Neo4j 公司成立&＃xff0c;标志着图计算进入了发展的阶段。

图计算研究真正开始的标志是 2004 年 Google 开发出面向大数据并行处理的计算模型MapReduce&＃xff0c;这一模型的推出给大数据并行处理带来了巨大的革命性影响。随后&＃xff0c;2006 年Apache Hadoop 团队引入了 Hadoop 分布式文件系统&＃xff08;HDFS&＃xff09;以及新的 Hadoop MapReduce框架。2009 年&＃xff0c;加州大学伯克利分校 AMP Lab 开发出 Spark 系统。

从2010年开始&＃xff0c;大规模分布式架构、多模态支持、图查询语言设计等图计算研究方向逐渐受到关注。Google 提出了 Pregel&＃xff0c;一个针对图算法特点设计的分布式图计算系统&＃xff0c;遵循 BSP 运算模型&＃xff1b;之后 CMU Select 实验室 GraphLab 项目组提出了GAS 运算模型。。虽然pregel 和 GraphLab 都是对于复杂机器学习计算的处理框架&＃xff0c;用于迭代型&＃xff08;iteration&＃xff09;计算&＃xff0c;但是二者的实现方法却采取了不同的路径&＃xff1a;Pregel 是基于大块的消息传递机制&＃xff0c;GraphLab 是基于内存共享机制&＃xff0c;对后续其他图计算系统的设计都产生了深远的影响。

Google在2012年5月提出了知识图谱的概念&＃xff0c;这是一种信息间全新的连接方式&＃xff0c;其基本组成单位是“实体—关系—实体”三元组&＃xff0c;实体之间通过关系相互联结&＃xff0c;构成网状的知识结构。知识图谱能够成立的核心是计算机的知识推理机制&＃xff0c;图计算为其提供了重要的底层技术支持。

2015年随着数据量级迅速增长&＃xff0c;应用市场逐渐打开&＃xff0c;对图计算系统扩展性和效率需求不断提高。中国图计算领域学术界和产业界研究开始逐渐发力&＃xff0c;发布了自己的图计算系统和平台 &＃xff0c;比如清华大学的Gemini等等。

近年来&＃xff0c;随着人工智能技术的发展&＃xff0c; 图神经网络也已经在业界展露身手了。

3.从框架模型看图计算

图计算的框架基本上都遵循BSP(Bulk Synchronous Parallell)的计算模式。BSP模式批量同步(bulk synchrony)机制&＃xff0c;其独特之处在于超步(superstep)概念的引入。一次计算过程由一系列全局超步组成&＃xff0c;每一个超步包含并行计算(local computation)、全局通信(非本地数据通信)以及栅栏同步(等待通信行为结束)三个阶段。

BSP模式有如下特点&＃xff1a;

1. 将计算划分为一个一个的超步(superstep)&＃xff0c;有效避免死锁;

2. 将处理器和路由器分开&＃xff0c;强调了计算任务和通信任务的分离&＃xff0c;而路由器仅仅完成点到点的消息传递&＃xff0c;不提供组装、复制和广播等功能&＃xff0c;既掩盖了具体的互连网络拓扑&＃xff0c;又简化了通信协议&＃xff1b;

3. 采用同步方式以硬件实现的全局同步和可控的粗粒度级&＃xff0c;执行紧耦合同步式并行算法。

一些有代表性的图计算框架如下&＃xff1a;

• Neo4j-APOC &＃xff1a;在图数据库的基础上&＃xff0c;支持一些基本图算法&＃xff0c;分布式版本不开源。

• Pregel &＃xff1a;Google 在 2009 年提出&＃xff0c;是图计算模型的开山祖师&＃xff0c;后续很多工作都受到它的思想影响。不开源。

• Giraph &＃xff1a;Facebook 基于 Pregel 思想的开源实现。

• Gemini &＃xff1a;清华大学基于 Pregel 思想进行了多项改进的实现&＃xff0c;性能优秀。仅提供免费 Demo&＃xff0c;商业版不开源。

• KnightKing &＃xff1a;针对 Walker 游走类算法专门设计的图计算框架&＃xff0c;不具有通用性。

• GraphX &＃xff1a;Apache 基金会基于 Spark 实现的图计算框架&＃xff0c;社区活跃度较高。

• GraphLab&＃xff08;PowerGraph&＃xff09;&＃xff1a;商业软件&＃xff0c;不开源。已被苹果收购。

• Plato &＃xff1a;腾讯基于 Gemini 和 KnightKing 思想的 C&＃43;&＃43; 开源实现&＃xff0c;是一款高性能、可扩展、易插拔的图计算框架。

4. 从算法看图计算

图算法指利用特指的顶点和边求得答案的一种简便方法&＃xff0c;无向图、有向图和网络能运用很多常用的图算法。对于图数据&＃xff0c;遍历算法&＃xff08;深度/广度优先&＃xff09;是其它算法的基础。典型的图算法有 PageRank、最短路径、连通分支、极大独立集、最小生成树以及 Bayesian Belief Propagation 等。图的最小生成树在生活中常代表着最低的成本或最小的代价&＃xff0c;常用 Prim 算法和 Kruskal 算法。社区发现、最短路径、拓扑排序、关键路径也都有对应的算法。

图算法包括了 搜索、匹配、分类、评估等多样化数据分析技术&＃xff0c;从算法结构维度大约可以分成两类&＃xff1a;以遍历为中心的算法和以计算为中心的算法。以遍历为中心的算法&＃xff0c;需要以特定方式从特定顶点遍历图&＃xff0c;存在着大量的随机访问。以计算为中心的算法&＃xff0c;需要在一个迭代周期中有大量的运算进行&＃xff0c;数据局部性相对较好。

5.从计算机体系结构看图计算

图计算一般都是数据驱动的计算&＃xff0c;计算结构无法在运行前准确地进行预测&＃xff0c;形态上没有明显规律&＃xff0c;难以高效优质地进行划分。现有的缓存机制往往只能对局部性好的数据访问提速&＃xff0c;大量数据的存取会使处理器频繁处于等待I/O的状态。

图计算的负载具有复杂性&＃xff0c;没有单一最具代表性的图计算负载。连接顶点的边&＃xff0c;只是无数可能连接中的一个小子集&＃xff0c;存在高度不规则性。在图计算的过程中&＃xff0c;读写的时空局部性难以掌握&＃xff0c;带宽占用情况难以预测。

大多数算法对内存带宽的占用可能不到50%&＃xff0c;是什么限制了内存带宽的利用呢&＃xff1f;处理器需获取指令&＃xff0c; 指令窗口间存在空间&＃xff0c;寄存器操作数需要等待&＃xff0c;直到操作数可用&＃xff0c;相关依赖才会解除。由于指令命中率较高&＃xff0c;可能导致内存层面的并行度下降&＃xff0c;难以充分利用平台的内存带宽。较低的缓存数据使用比又意味着应用难以从空间局 部性中获利&＃xff0c;数据预取策略会失效。数据预取一般对提升性能有帮助&＃xff0c;但也会生成大量无用的预取操作。对于内存带宽或者说缓存容量有限的应用来说&＃xff0c;数据预取可能造成一定资源浪费。在多线程计算的情况下&＃xff0c;若触发延迟较高的远程内存访问&＃xff0c;也会抵消多线程的收益。

图计算需要怎样的处理器核心呢&＃xff1f;一般地&＃xff0c;会采用许多小计算核心加高线程数的架构&＃xff0c;适合处理传统多核处理器所不擅长的大图计算。在多图并发计算的时候&＃xff0c;有共享分配与独占分配两种策略。共享分配策略指将 m 项请求中的每一项都使用 n 个逻辑核心并行处理&＃xff0c;由OS管理不同请求在逻辑核心上的切换。独占分配策略指为每一项请求分配 n/m 个逻辑核心&＃xff0c;使逻辑核心不需要在任务间切换。独占分配策略更适合并发图计算&＃xff0c;独占通常可减少相同并发请求下整体的运行时间。重排序缓存竞争度低可能是独占策略在并发图计算场景中优于共享策略的原因。

就图计算产生的功耗而言&＃xff0c;负载变化导致系统功率波动&＃xff0c;会出现峰谷交错的情形。若增加并发任务&＃xff0c;会改变峰谷比率并抬升功耗。一般地&＃xff0c;对CPU的功耗而言&＃xff0c;以计算为中心的算法平均每条指令能耗大&＃xff0c;以遍历为中心的算法则相反&＃xff1b;对内存的功耗而言&＃xff0c;以计算为中心的算法内存的平均能耗小&＃xff0c;以遍历为中心的算法则相反。

大多基于图计算的应用都是内存受限的&＃xff0c;但也存在受核心部件限制带来的内存利用率不足。足够的活跃线 程创造并发访问&＃xff0c;或可提升利用率。更多线程是需要的&＃xff0c;但由于线程间不均衡性&＃xff0c;可能使用起来效率不高&＃xff0c;需要提供更可扩展的并行策略&＃xff0c;来优化多核处理器的高带宽内存使用。功耗和能耗行为从指令角度和顶点计算角度来看都各有不同&＃xff0c;需要精准的功耗管理方法&＃xff0c;粗放型调整恐难起到作用。

6.从系统看图计算

依据大规模图计算系统的使用场景以及计算平台架构的不同&＃xff0c;可以将其分为单机内存图计算系统、单机外存图计算系统、分布式内存图计算系统和分布式外存图计算系统。

单机内存图处理系统就是图处理系统运行在单机环境&＃xff0c;并且将图数据全部缓冲到内存当中。单机外存图处理系统就是图处理系统运行在单机环境&＃xff0c;并且通过计算将图数据不断地与内存和磁盘进行交互的高效图算法。分布式内存系统就是图处理系统运行在分布式集群环境&＃xff0c;并且所有的图数据加载到内存当中。分布式外存图计算系统将单机外存系统&＃xff08;Singlemachine out-of-core systems&＃xff09;拓展为集群&＃xff0c;能够处理边的数量级为 trillion 的图。

7. 从AI 看图计算

AI 和图计算融合产生的图神经网络&＃xff08;GNN&＃xff09;&＃xff0c;是目前正在快速发展且重要的领域。各种实体之间的关系数据&＃xff0c;它怎么和神经网络进行结合&＃xff1f;图神经网络&＃xff0c;利用了表示学习&＃xff0c;通过图的结构先把每一个节点或者边都用向量来表示特征&＃xff0c;然后再进一步地使用神经网络来处理。这就扩展了神经网络使用的范围&＃xff0c;把实体之间的关系也引入到 AI 的处理中。

图神经网络可以看作一个图特征的学习过程&＃xff0c;比如节点的代表特征或者图级的代表特征&＃xff0c;一般以图的属性和图的结构作为输入&＃xff0c;输出一组更新后的节点表示。一般这个过程也称作图滤波操作。图滤波会更新节点特征但不会改变图的结构。图神经网络的发展是从不同的理论动机中发展出来的&＃xff0c;比如&＃xff0c;将GNN看作为非欧距离的卷积推广&＃xff0c;那它是基于图信号发展起来的&＃xff1b;现在大多的GNN基于神经消息传递方法是通过类比图模型中概率推理的消息传递算法提出的。

不管是谱方法还是基于空间的思想&＃xff0c;图神经网络最后都可统一到基于消息传递的框架下。GNN消息传递框架基本思想是在每次迭代时&＃xff0c;每个节点都聚合其邻居节点的信息。随着迭代次数的增加&＃xff0c;每个节点包含图上更大范围的信息。比如&＃xff0c;经过k次迭代后&＃xff0c;中心节点可以获取其k跳邻域的信息。其关键思想是基于图结构和已知的特征信息生成节点表示。GNN利用了图上的结构和节点特征信息&＃xff0c;生成深层的嵌入表示&＃xff0c;而传统的图嵌入方法只利用了图的结构信息&＃xff0c;通过查表的方式生成层嵌入。

7.1 GNN VS MLP/CNN/RNN

图数据中结点邻居具有两个特点&＃xff0c;一是数量不定&＃xff0c;二是顺序不定&＃xff0c;因此MLP/CNN/RNN无法直接处理这样的非欧式数据而只能用GNN建模。实际上&＃xff0c;可以将GNN看做一种更加泛化的模型&＃xff0c;例如&＃xff0c;RNN相当于线性图上的GNN&＃xff0c;而Transformer相当于完全图上的GNN。

7.2 GNN VS Graph Embedding

在GNN之前已经涌现出很多Graph Embedding方法&＃xff0c;并被广泛应用在搜索类服务的向量召回阶段&＃xff0c;这类方法受Word2vec启发设计&＃xff0c;从最初的的Item2Vec到Node2Vec基于平衡同质性和结构性的改进&＃xff0c;再到MetaPath2Vec基于对图的异构性改进&＃xff0c;以及引入属性数据缓解行为数据的稀疏性&＃xff0c;这类方法都遵循着Skip-Gram的范式。

相比于这些方法&＃xff0c;GNN可以结合目标任务端到端地进行训练&＃xff0c;而Graph Embedding更像是预训练&＃xff0c;其学习到的Embedding不一定与目标任务相关&＃xff0c;特别是在样本规模庞大的业务场景&＃xff0c;端到端训练得到的Embedding比预训练得到的Embedding更有效。

GNN的层级网络结构方便与其他深度学习技术结合&＃xff0c;例如GCN&＃43;Attention&＃61;GAT。GNN可以适用Inductive的任务&＃xff0c;即当图的结构发生变化后&＃xff0c;加入了一些新的结点&＃xff0c;如果是Graph Embedding方法就需要重新训练模型&＃xff0c;而GNN可以使用类似GraphSage Node-Wise Sampling的方式&＃xff0c;使用已经训练好的模型直接对新的结点进行推断&＃xff0c;在消息传递的过程中可以使用多种特征。

7.3 GNN VS Feature Concat & Collaborative Filtering & Proximity Loss

Feature Concat表示将特征拼接到一起然后通过特征交叉可以学习到一阶的属性关联信息。Collaborative Filtering也可以通过用户历史行为学习到一阶的行为关联信息。Proximity Loss表示在损失函数中加入正则项使得相邻的结点更相似&＃xff0c;但是一方面它是一种隐式的方式&＃xff0c;另一方面想确保学习到高阶的相似关系&＃xff0c;就需要加入更复杂的K阶正则项&＃xff0c;这也是GCN提出时的出发点之一。相比这三种方法&＃xff0c;GNN可以通过堆叠多层显示地学习高阶的关联信息。

图神经网络的设计中有个关键的条件要满足就是置换不变性或者置换等变性&＃xff0c;就是设计的函数在处理图数据时&＃xff0c;不受节点顺序的影响&＃xff0c;或者输入时的顺序变换域输出的顺序一致。

8. 小结

图是一种最为灵活的连接方式&＃xff0c;让实体之间可以不受限制地连接。图计算是研究在大量数据中如何高效计算、存储并管理图数据等问题的领域&＃xff0c;可以应用于相当广泛的业务场景&＃xff0c;如资本市场风险管理、生命科学研究、医疗保健交付、监控和应对道路事故、智能基础设施管理扽等。高效处理大规模数据的图计算&＃xff0c;能推动社交网络分析、语义 web 分析、生物信息网络分析、自然语言处理等新兴应用领域的发展。

【参考资料与关联阅读】 

• “人工智能之图计算”&＃xff0c;清华大学人工智能研究院&＃xff0c;北京智源人工智能研究院&＃xff0c;清华-工程院知识智能联合研究中心&＃xff0c;2019-2

• https://zhuanlan.zhihu.com/graphComputing

• https://www.zhihu.com/column/c_1496512305013219328

• https://www.aminer.cn/oag2019

• https://www.oreilly.com/library/view/graph-algorithms/9781492047674

• 有向无环图&＃xff08;DAG&＃xff09;的温故知新

• 知识图谱的5G追溯

• 从语义网到知识图谱

• 行业规模的知识图谱——经验和挑战

• 知新温故&＃xff0c;从知识图谱到图数据库

• 感知人工智能操作系统

• 老码农的AI漫谈

• 面向AI 的数据生态系统

• AI系统中的偏差与偏见

• AI 语音交互开放平台的构建与演进

• 揭秘“语音交互”背后的AI硬核黑科技&＃xff01;

• 老码农眼中的简明AI